5.
An algorithm for solving the satisfiability problem is presented. It is proved that this algorithm solves 2-SAT and Horn-SAT
in linear time and
k-positive SAT (in which every clause contains at most
k positive literals) in time
O(|
F|·ξ
n
k
), where |
F| is the length of input
F, n is the number of atoms occurring in
F, and ξ
k
is the greatest real number satisfying the equation
. Compared with previous results, this nontrivial upper bound on time complexity could only be obtained for
k-SAT, which is a subproblem of
k-positive SAT.
Research partially supported by NSFC grant 221-4-1439.
HUANG Xiong received his B.S. and M.S. degrees in computer science from Peking University in 1992 and 1995 respectively. Now he is a
Ph.D. candidate in Beijing University of Aeronautics and Astronautics. His major research interests are design and analysis
of algorithms, computational complexity, and satisfiability problem.
LI Wei received his B.S. degree in mathematics from Peking University in 1966 and his Ph.D. degree in computer science from The
University of Edinburgh in 1983. Since 1986, he has been a Professor in computer science at Beijing University of Aeronautics
and Astronautics. He has published over 100 papers in the areas of concurrent programming languages, operational semantics,
type theory, and logical foundation of artificial intelligence.… …
相似文献